1. Field of the Invention
The present invention relates generally to an interleaving/deinterleaving device and method, and in particular, to an interleaving/deinterleaving device and method for a turbo encoder used in radio communication systems such as satellite, ISDN (Integrated Services Digital Network), digital cellular, W-CDMA (Wideband Code Division Multiple Access), IMT-2000 and W-ATM (Wideband Asynchronous Transfer Mode) communication systems.
2. Description of the Related Art
In a turbo encoder, interleaving is performed to randomize information input to the encoder and to improve the distance property of a codeword. In particular, it is expected that the turbo encoder will be used in a supplemental channel (or traffic channel) of an IMT-2000 (or CDMA-2000) communication system and in a data channel of UMTS (Universal Mobile Telecommunication System) proposed by ETSI (European Telecommunication Standards Institute). Thus, a method for embodying an interleaver for this purpose is required. In addition, the use of turbo encoders results in an increase in the reliability of a digital communication system, and in particular, to a performance improvement of existing and future digital mobile communication systems.
The turbo encoder encodes an input frame of L information bits into parity symbols using two simple parallel concatenated codes, wherein recursive systematic convolutional (RSC) codes are typically used for component codes.
FIG. 9 shows a common turbo encoder, which is disclosed in detail in U.S. Pat. No. 5,446,747, issued on Aug. 29, 1995, which is hereby incorporated by reference.
Referring to FIG. 9, the turbo encoder includes a first component encoder 11 for encoding input frame data, an interleaver 12 for interleaving the input frame data, and a second component encoder 13 for encoding an output of the interleaver 12. A known RSC encoder is typically used for the first and second component encoders 11 and 13. Further, the interleaver 12 has the same size as the input information bit frame, and rearranges the sequence of the information bits provided to the second component encoder 13 to reduce a correlation between the information bits.
For the internal interleaver (or a turbo interleaver) 12 of the turbo encoder, there are proposed various interleavers such as PN (Pseudo Noise) random interleaver, random interleaver, block interleaver, non-linear interleaver, and S-random interleaver. However, so far, such interleavers are mere algorithms designed to improve their performances in terms of scientific researches rather than implementation. Therefore, when implementing an actual system, the hardware implementation complexity must be taken into consideration. A description will now be made of properties and problems associated with the conventional interleaver for the turbo encoder.
Performance of the turbo encoder is dependent upon the internal interleaver. In general, it is not possible to design an interleaver guaranteeing an optimal performance because an increase in interleaver size causes a geometric increase in calculations. Therefore, in general, the interleavers are implemented by determining conditions satisfying several given criteria. The criteria are as follows:
Distance Property: The distance between adjacent codeword symbols should be maintained to a certain extent. Since this has the same function as a codeword distance property of the convolutional code, it is preferable that the interleaver should be designed to have the longer distance, if possible.
Weight Property: A weight of a codeword corresponding to a non-zero information word should be higher than a threshold value. Since this has the same function as the minimum distance property of the convolutional code, it is preferable that the interleaver should be designed to have the greater weight, if possible.
Random Property: A correlation factor between output word symbols after interleaving should be much lower than a correlation factor between original input word symbols before interleaving. That is, randomization between the output word symbols should be completely performed. This makes a direct effect on the quality of extrinsic information generated in continuous decoding.
Although the above three design criteria are applied to the turbo interleaver, the properties are not definitely analyzed. According to experiments, the random interleaver is superior in performance to the block interleaver. However, the random interleaver is disadvantageous in that an increase in the variety and size of the frame causes an increase in the required memory capacity for storing an interleaver index (i.e., mapping rule or address). Therefore, taking the hardware size into consideration, it is preferable to employ an enumeration method for reading data stored at a corresponding address by generating an address at every symbol clock using an index generating rule rather than a look-up table method for storing the interleaver index.
In conclusion, when various interleaver sizes are required and the hardware implementation complexity is limited in the IMT-2000 or UTMS system, the turbo interleaver should be designed to guarantee the optimal interleaver performance by taking the limitations into consideration. That is, it is necessary to define an address generating rule and then perform interleaving/deinterleaving according to the address generating rule. Of course, the interleaver should be designed to completely satisfy the above stated turbo interleaver""s properties.
The IMT-2000 or UMTS specification has not yet given any definition to the turbo interleaver. The forward link and the reverse link defined by the IMT-2000 specification have various types of logical channels and various interleaver sizes. Therefore, in order to meet this variety requirement, there is required an increase in memory capacity. For example, in a N=3 forward link transmission mode, an interleaver of various sizes ranging from 144 bits/frame to 36864 bits/frame may be used.
To sum up, the prior art has the following disadvantages.
First, for the conventional internal interleaver of the turbo encoder, PN random interleavers, random interleavers, block interleavers, non-linear interleavers, and S-random interleavers may be used. However, such interleavers are mere algorithms designed to improve their performances in terms of scientific researches rather than implementation. Therefore, when implementing an actual system, the hardware implementation complexity of such interleavers must be considered. However, this is not specifically defined.
Second, since a controller (CPU or host) of the transceiver should store interleaving rules according to the respective interleaver sizes in the existing interleaving method using a look-up table, a host memory requires a separate capacity in addition to an interleaver buffer. That is, when the frame size becomes varies and increases in size, an increased memory capacity for storing the interleaver index (i.e., mapping rule or address) is required.
Third, it is not easy to implement an interleaver satisfying both the distance property and the random property.
Fourth, a detailed turbo interleaver design specification for the turbo encoder of the CDMA-2000 forward link is not established yet.
It is, therefore, an object of the present invention to provide a device and method for implementing an interleaver which can solve the problems of the conventional interleaver.
It is another object of the present invention to provide an interleaving/deinterleaving device and method satisfying all the properties of a turbo encoder, including the distance property, weight property and random property, in a communication system.
It is further another object of the present invention to provide a device and method for performing interleaving using a virtual address area having a size of 2mxc3x97N (where N is an integer, and M is larger than 1 and equal to the number of shift registers) by adding a specific value to an input data size value, in a communication system.
To achieve the above objects, there is provided a method for interleaving input data having a size other than multiples of 2m (m greater than 1). The method comprises sequentially storing input data in a memory; adding an offset value to the input data size to provide a virtual address having a size of 2m; defining a plurality of address generation areas each having a size of 2m, generating random addresses in the address generation areas; and reading the input data from the memory using the random addresses generated from the address generation areas.